package finalED.util.dataStructures.AVL;

/**
 * 
 * @author Oswaldo.C
 */
public class AVLTree<E extends Object & Comparable> {

    /** 
     * An empty node as super root. The real AVLTree is rooted in the
     * <code>rootAbove</code>'s leftNode link. It's useful for mantaining
     * an implicit pointer to parent nodes.
      */
    private AVLNode<E> rootAbove;

    /**
     * 
     * Creates a new AVLTree with a single empty node as root.
     */
    public AVLTree() {
        rootAbove = new AVLNode();
    }

    /**
     * @param rotateBase: The root of the subtree that is being rotated
     * @param rootAbove: The AVLNode that points to rotateBase (parent)
     *
     * This method rotates the subtree balancing it.
     * */
    private void rotate(AVLNode<E> rotateBase, AVLNode<E> rootAbove) {

        //calculates the BF
        int balance = rotateBase.getBalance();

        if (Math.abs(balance) < 2) {
            System.out.println("No rotate");
        }

        //gets the child on the side with the greater height
        AVLNode<E> child = (balance < 0) ? rotateBase.getLeftNode() : rotateBase.getRightNode();


        if (child == null) {
            return;
        }

        int childBalance = child.getBalance();
        AVLNode<E> grandChild = null;

        //both the child and grandchild are on the
        //left side, so rotate the child up to the root position
        if (balance < -1 && childBalance < 0) {
            if (rootAbove != this.rootAbove && rootAbove.getRightNode() == rotateBase) {
                rootAbove.setRightNode(child);
            } else {
                rootAbove.setLeftNode(child);
            }

            grandChild = child.getRightNode();
            child.setRightNode(rotateBase);
            rotateBase.setLeftNode(grandChild);
            return;
        } //both the child and the grandchild are on the
        //right side, so rotate the child up to the root position
        else if (balance > 1 && childBalance > 0) {
            if (rootAbove != this.rootAbove && rootAbove.getRightNode() == rotateBase) {
                rootAbove.setRightNode(child);
            } else {
                rootAbove.setLeftNode(child);
            }

            grandChild = child.getLeftNode();
            child.setLeftNode(rotateBase);
            rotateBase.setRightNode(grandChild);
            return;
        } //the child is on the left side, but the grandchild is on the
        //right side, so rotate the grandchild up to the child position
        //so the condition of the first if statement is satisfied,
        //then recurse to have the first if statement evaluated
        else if (balance < -1 && childBalance > 0) {
            grandChild = child.getRightNode();
            rotateBase.setLeftNode(grandChild);
            child.setRightNode(grandChild.getLeftNode());
            grandChild.setLeftNode(child);
            rotate(rotateBase, rootAbove);
            return;
        } //the child is on the right side, but the grandchild is on the
        //left side, so rotate the grandchild up to the child position
        //so the condition of the second if statement is satisfied,
        //then recurse to have the second if statement evaluated
        else if (balance > 1 && childBalance < 0) {
            grandChild = child.getLeftNode();
            rotateBase.setRightNode(grandChild);
            child.setLeftNode(grandChild.getRightNode());
            grandChild.setRightNode(child);
            rotate(rotateBase, rootAbove);
            return;
        }

    }

    /**
     * @param element: The element to insert into the Tree
     *
     * This method invokes a private helper method to insert the element.
     * It passes the root as the place to start.
     * */
    public void insert(E element) {
        insert(element, rootAbove.getLeftNode());
    }

    /**
     * @param element: The element to insert into the Tree
     * @param node: The AVLNode to evaluate for recursive insertion
     *
     * This method recursively traverses the Tree, inserting the
     * element at the appropriate spot and incrementing the balance
     * factors for the subtrees as it evaluates. The Tree will then
     * recursively rebalance as necessary.
     * */
    private void insert(E element, AVLNode<E> temp) {
        if (this.rootAbove.getLeftNode() == null) {
            this.rootAbove.setLeftNode(new AVLNode<E>(element));
            return;
        }

        //travel left or right based on the
        //comparison of element to node.element
        //remember that left means that element <= node.element
        //and right means element > node.element
        int compare = element.compareTo(temp.getData());


        //travel to the left of the Tree, inserting
        //if the bottom has been reached
        if (compare <= 0) {

            //System.out.println(node.getLeft());
            if (temp.getLeftNode() == null) {
                temp.setLeftData(element);
                return;
            }

            insert(element, temp.getLeftNode());
        } //otherwise, travelling to the right of the Tree,
        //inserting if the bottom has been reached
        else {

            if (temp.getRightNode() == null) {
                temp.setRightData(element);
                return;
            }

            insert(element, temp.getRightNode());

        }

        //if the root is being evaluated it, rotate if necessary
        if (temp == rootAbove.getLeftNode()) {
            rotate(rootAbove.getLeftNode(), rootAbove);
        }

        //otherwise, rotate the left and right subtrees
        //as necessary
        if (temp.getLeftNode() != null) {
            rotate(temp.getLeftNode(), temp);
        }

        if (temp.getRightNode() != null) {
            rotate(temp.getRightNode(), temp);
        }


    } //end insert

    public void remove(E element) {
        remove(element, rootAbove);
    }

    /**
     * @param element: The element to remove from the AVLTree
     * @param node: The root node of the subtree
     *
     * This method recursively traverses the AVLTree based on
     * the ordering of the element with respect to the Tree's
     * elements. If the element is not found, then nothing happens.
     * Otherwise, the element is removed, and either the far-right
     * element on its left child or the far left element on its right
     * child replaces it.
     ***/
    private void remove(E element, AVLNode<E> temp) {
        if (temp == null) {
            return;
        }

        int compare = 0;

        if (temp != rootAbove) {
            compare = element.compareTo(temp.getData());
        }

        boolean direction = (compare > 0 && temp != rootAbove);

        AVLNode<E> child = direction ? temp.getRightNode() : temp.getLeftNode();

        //element not found
        if (child == null) {
            return;
        }

        //if the root is perfectly balanced, slide the left Node up
        //and reinsert the left.right element if necessary
        if (temp == rootAbove && child.getBalance() == 0
                && child.getData().equals(element)) {

            AVLNode<E> newRoot = child.getLeftNode();

            if (newRoot == null) {
                rootAbove.setLeftNode(null);
                return;
            } else {
                enactRemoval(temp, child, false);
                return;
            }
        } //if the element is found and the root is not
        // perfectly balanced, remove it using enactRemoval()
        else if (element.compareTo(child.getData()) == 0) {
            enactRemoval(temp, child, direction);
        } //otherwise, recursively traverse the tree
        else {
            remove(element, child);
        }

    }

    /**
     * @param parent: The parent of the element to be removed
     * @param remove: The element to remove from the Tree
     * @param direction: false if remove is to the left of parent, true otherwise
     *
     * This method physically removes the AVLNode with the element from the
     * AVLTree, replacing it with the appropriate successor.
     ***/
    private void enactRemoval(AVLNode<E> parent, AVLNode<E> remove, boolean direction) {
        AVLNode<E> temp = null;
        AVLNode<E> left = remove.getLeftNode();
        AVLNode<E> right = remove.getRightNode();

        //if the Node to remove is not a leaf, find the appropriate successor
        if (left != null || right != null) {
            temp = findSuccessor(remove);
        }

        //if remove is the right child of parent, update parent's right node
        if (direction && (parent != rootAbove)) {
            parent.setRightNode(temp);
        } //otherwise, update its left node with the successor
        else {
            parent.setLeftNode(temp);
        }

        //and update node to point to remove's children
        if (temp != null) {

            if (temp != left) {
                temp.setLeftNode(remove.getLeftNode());
            }

            if (temp != right) {
                temp.setRightNode(remove.getRightNode());
            }
        }

        //and finally, discard those references from remove
        //so that the removed Node is garbage collected sooner
        remove.setLeftNode(null);
        remove.setRightNode(null);
    }

    /**
     * @param root: The element for which to find a successor AVLNode
     * @return AVLNode<E>: The successor Node
     ***/
    private AVLNode<E> findSuccessor(AVLNode<E> root) {
        AVLNode<E> temp = root;
        AVLNode<E> parent = null;

        //if the balance favors the right, traverse right
        //otherwise, traverse left
        boolean direction = (temp.getBalance() > 0);

        parent = temp;
        temp = (direction) ? temp.getRightNode() : temp.getLeftNode();

        if (temp == null) {
            return temp;
        }

        //and find the farthest left-Node on the right side,
        //or the farthest right-Node on the left side
        while ((temp.getRightNode() != null && !direction)
                || (temp.getLeftNode() != null && direction)) {

            parent = temp;
            temp = (direction) ? temp.getLeftNode() : temp.getRightNode();
        }



        //finally, update the successor's parent's references
        //to adjust for a left child on the right node, or a right
        //child on the left-node
        if (temp == parent.getLeftNode()) {
            parent.setLeftNode(temp.getRightNode());
            temp.setRightNode(null);
        } else {
            parent.setRightNode(temp.getLeftNode());
            temp.setLeftNode(null);
        }

        return temp;
    }

    /**
     * @param element: The element to search for in the AVLTree
     * @return boolean: true if the element is found, false otherwise
     *
     * The contains method simply traverses the binary search tree based on
     * element's relation to the AVLNodes in the Tree until a match is found
     * or it hits the bottom of the Tree.
     * */
    public boolean lookup(E element) {

        //begin with the real root
        AVLNode<E> node = rootAbove.getLeftNode();

        while (node != null) {
            if (node.getData().equals(element)) {
                //found
                return true;
            }

            int balance = element.compareTo(node.getData());
            node = (balance < 0) ? node.getLeftNode() : node.getRightNode();
        }

        //not found
        return false;
    }

    public void inorder(AVLNode<E> tmp) {
        if (tmp != null) {
            inorder(tmp.getLeftNode());
            System.out.println(tmp.getData());
            inorder(tmp.getRightNode());
        }
    }

    public static void main(String[] args) {
        AVLTree<Integer> avl = new AVLTree<Integer>();
        avl.insert(6);
        avl.insert(76);
        avl.insert(19);
        avl.insert(87);
        avl.insert(-8);
        avl.insert(6);


        avl.inorder(avl.rootAbove.getLeftNode());

        assert (avl.lookup(5) == false);
        assert (avl.lookup(100) == false);
        assert (avl.lookup(6) == true);
        assert (avl.lookup(90) == false);
        assert (avl.lookup(-8) == true);
        assert (avl.lookup(19) == true);
        assert (avl.lookup(87) == true);

        avl.remove(-8);
        avl.remove(6);
        avl.remove(87);
        avl.remove(19);
        avl.remove(6);

        System.out.println("Despues de eliminar");

        avl.inorder(avl.rootAbove.getLeftNode());
        
        
    }
} //End Class AVLTree
